//: [Previous](@previous)

/*:
 # 计数排序
 * 最好情况 O(n+k))
 * 最坏情况 O(n+k))
 * 平均时间复杂度 O(n+k))
 * 空间复杂度 O(k)
 
 1. 先找出最大的数和最小的数
 2. 开辟一块新的空间创建新的数组 B，长度为 ( max - min + 1)
 3. 数组 B 中 index 的元素记录的值是 A 中某元素出现的次数
 4. 最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数
 
 */

import Foundation

var numbers = [3, 6, 5, 2, 7, 9, 1, 4, 3]
print("排序前 \(numbers)")

func countingSort(_ arr: [Int]) -> [Int] {
    if arr.count < 2 {
        return arr
    }
    
    var min = arr[0], max = arr[0]
    for i in 1..<arr.count {
        if max < arr[i] {
            max = arr[i]
        }
        if min > arr[i] {
            min = arr[i]
        }
    }
    
    var indexs = Array(repeating: 0, count: max-min+1)
    for item in arr {
        indexs[item-min] += 1
    }
    
    var nums: [Int] = []
    for i in 0..<indexs.count {
        nums += Array(repeating: i+min, count: indexs[i])
    }
    
    return nums
}

print("计数排序后 \(countingSort(numbers))")

//: [Next](@next)
